#define INC_COUNT 5
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "seqlist.h"

int seqlist_init(seq_t **li_ptr, int capacity, int size)
{
	seq_t *me = NULL;

	me = malloc(sizeof (seq_t));
	if (NULL == me)
		return -1;

	me->arr = calloc(capacity, size);
	if (NULL == me->arr) {
		free(me);
		return -1;
	}
	
	me->capacity = capacity;
	me->size = size;
	me->nmemb = 0;

	*li_ptr = me;

	return 0;
}

int seqlist_is_full(const seq_t *li)
{
	return li->nmemb == li->capacity;
}

static int __insert_memb(seq_t *li, const void *data, int pos)
{
	if (pos <= li->nmemb) {
		// 将pos到最后的所有元素向后挪
		memmove((char *) li->arr + (pos + 1) * li->size, \
				(char *) li->arr + pos * li->size, \
				(li->nmemb - pos) * li->size);
		// 插入data元素
		memcpy((char *) li->arr + pos * li->size, data, li->size);

		li->nmemb++;

		return 0;
	} else {
		return -1;
	}
}

int seqlist_insert_tail(seq_t *li, const void *data)
{
	if (seqlist_is_full(li)) {
		li->arr = realloc(li->arr, (li->capacity + INC_COUNT) * li->size);
		if (NULL == li->arr) {
			return -1;
		}
		li->capacity += INC_COUNT;
	}
	
	__insert_memb(li, data, li->nmemb);

	return 0;
}

int seqlist_insert_head(seq_t *li, const void *data)
{
	
	if (seqlist_is_full(li)) {
		li->arr = realloc(li->arr, (li->capacity + INC_COUNT) * li->size);
		if (NULL == li->arr) {
			return -1;
		}
		li->capacity += INC_COUNT;
	}
	
	__insert_memb(li, data, 0);

	return 0;
}

int seqlist_insert_sort(seq_t *li, const void *data, cmp_t cmp)
{
	int i;

	if (seqlist_is_full(li)) {
		li->arr = realloc(li->arr, (li->capacity + INC_COUNT) * li->size);
		if (NULL == li->arr) {
			return -1;
		}
		li->capacity += INC_COUNT;
	}
	//printf("Copy %p to %p (%dB)\n", data, (char *) li->arr + li->nmemb * li->size, li->size);
	//memcpy((char *) li->arr + li->nmemb * li->size, data, li->size);
	
	for (i = li->nmemb - 1; i >= 0; i--) {
		if (cmp((char *) li->arr + li->size * i, data) > 0) {
			memmove((char *) li->arr + li->size * (i + 1), (char *) li->arr + li->size * i, li->size);
		} else {
			break;
		}
	}

	// 插入待插入元素
	memcpy((char *) li->arr + li->size * (i + 1), data, li->size);
	li->nmemb++;

	return 0;
}

void *seqlist_find(const seq_t *li, const void *key, cmp_t cmp)
{
	int i;
	char *addr;

	for (i = 0; i < li->nmemb; i++) {
		addr = (char *) li->arr + i * li->size;
		if (0 == cmp((void *) addr, key)) {
			return (void *) addr;
		}
	}

	return NULL;
}

int seqlist_delete(seq_t *li, const void *key, cmp_t cmp)
{
	void *f = NULL;
	int del_pos;
	int decrease;

	f = seqlist_find(li, key, cmp);
	if (NULL == f) {
		return -1;
	}

	del_pos = ((char *) f - (char *) li->arr) / li->size;

	memcpy(f, (char *) f + li->size,
			(li->nmemb - del_pos - 1) * li->size);

	li->nmemb--;

	if ((li->capacity - li->nmemb) > INC_COUNT) {
		decrease = (li->capacity - li->nmemb) - INC_COUNT;
		li->capacity -= decrease;
		li->arr = realloc(li->arr, li->capacity * li->size);
		if (NULL == li->arr) {
			return -1;
		}
	}

	return 0;
}

int seqlist_fetch(seq_t *li, const void *key, cmp_t cmp, void *data)
{
	void *f = NULL;
	int del_pos;
	int decrease;

	f = seqlist_find(li, key, cmp);
	if (NULL == f) {
		return -1;
	}

	del_pos = ((char *) f - (char *) li->arr) / li->size;

	memcpy(data, (char *) li->arr + del_pos * li->size, li->size);

	memcpy(f, (char *) f + li->size,
			(li->nmemb - del_pos - 1) * li->size);

	li->nmemb--;

	if ((li->capacity - li->nmemb) > INC_COUNT) {
		decrease = (li->capacity - li->nmemb) - INC_COUNT;
		li->capacity -= decrease;
		li->arr = realloc(li->arr, li->capacity * li->size);
		if (NULL == li->arr) {
			return -1;
		}
	}

	return 0;
}

void seqlist_travel(const seq_t *li, print_t print)
{
	int i;

	for (i = 0; i < li->nmemb; i++) {
		print((char *) li->arr + i * li->size);
	}
}

void seqlist_destroy(seq_t **li_ptr)
{
	if (NULL == *li_ptr) {
		return;
	}

	free((*li_ptr)->arr);
	(*li_ptr)->arr = NULL;

	free(*li_ptr);
	*li_ptr = NULL;
}

